''Rush Hour'' is a

sliding block puzzle A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide (frequently flat) pieces along certain routes (usually on a board) to establish a certain end-configuration. The pieces to ...

invented by

Nob Yoshigahara Nobuyuki Yoshigahara ( ''Yoshigahara Nobuyuki'', commonly known as "Nob"; May 27, 1936 – June 19, 2004) was perhaps Japan's most celebrated inventor, collector, solver, and communicator of puzzles. Nob graduated from the Tokyo Institute of ...

in the 1970s. It was first sold in the

United States The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...

in 1996. It is now being manufactured by

ThinkFun ThinkFun, formerly known as Binary Arts, is a toy and board game company founded in 1985 by Bill Ritchie and Andrea Barthello. The two started the company from the basement of their home in Virginia, with a product base that initially consisted of ...

(formerly Binary Arts). ThinkFun now sells ''Rush Hour'' spin-offs ''Rush Hour Jr.'', ''Safari Rush Hour'', ''Railroad Rush Hour'', ''Rush Hour Brain Fitness'' and ''Rush Hour Shift'', with puzzles by

Scott Kim Scott Kim is an American puzzle and video game designer, artist, and author of Korean descent. He started writing an occasional "Boggler" column for ''Discover'' magazine in 1990, and became an exclusive columnist in 1999, and created hundreds of ...

Game

The board is a 6×6 grid with grooves in the tiles to allow cars to slide, card tray to hold the cards, current active card holder and an exit hole. The game comes with 16 vehicles (12 cars, 4 trucks), each colored differently, and 40 puzzle cards. Cars and trucks are both one square wide, but cars are two squares long and trucks are three squares long. Vehicles can only be moved along a straight line on the grid; rotation is forbidden. Puzzle cards, each with a level number that indicates the difficulty of the challenge, show the starting positions of cars and trucks. Not all cars and trucks are used in all challenges.

Objective

The goal of the game is to get only the red car out through the exit of the board by moving the other vehicles out of its way. However, the cars and trucks (set up before play, according to a puzzle card) obstruct the path which makes the puzzle even more difficult.

Editions

The Regular Edition comes with forty puzzles split into four different difficulties, ranging from Beginner to Expert. The Deluxe Edition has a black playing board, card box in place of the Regular Edition's card tray, and sixty new puzzles with an extra difficulty: the Grand Master. The Ultimate Collector's Edition has a playing board that can hold vehicles not in play and can display the active card in a billboard-like display. The Ultimate Collectors Edition also includes 155 new puzzles (with some of them being from card set three) and a white limo. In 2011, the board was changed to black, like the Deluxe Edition. An

iOS iOS (formerly iPhone OS) is a mobile operating system created and developed by Apple Inc. exclusively for its hardware. It is the operating system that powers many of the company's mobile devices, including the iPhone; the term also includes ...

version of the game was released in 2010.

Expansions

Three official expansions, called "add-on packs", were released: Card Set 2, which comes with a red sports car that takes up 2 squares; Card Set 3, which comes with a white limo that takes up 3 squares; and Card Set 4, which comes with a taxi that takes up 2 squares. Each set also comes with 40 new exclusive challenges—from Intermediate to Grand Master—that make use of the new vehicles in place of (or in addition to) the red car. All three of the expansion packs will work with all editions of the game. Also, like the Regular Edition of the game in 2011, the cards of all three expansions were changed to have new levels and design to match the new board color of the Regular Edition.

Computational complexity on larger boards

Rush Hour solution - hardest configuration

When generalized so that it can be played on an arbitrarily large board, the problem of deciding if a ''Rush Hour'' problem has a solution is

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...

. This is proved by reducing a graph game called

nondeterministic constraint logic In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in ...

, which is known to be PSPACE-complete, to generalized Rush Hour positions. In 2005, Tromp and Cilibrasi showed that ''Rush Hour'' is still PSPACE-complete when the cars are of size 2 only. They also conjectured that ''Rush Hour'' is still nontrivial when the cars are of size 1 only.

Most difficult configurations

The hardest possible initial configuration has been shown to take 93 steps. A shortest solution can be seen on the right. If you count the necessary moves instead of the steps, the most difficult start configuration in this sense requires 51 moves.Michael Fogleman (July 2018)
"Solving Rush Hour, the Puzzle"
How I created a database of all interesting Rush Hour configurations.

References

Mechanical puzzles Combination puzzles Mensa Select winners Puzzle video games PSPACE-complete problems Single-player games